package Top_Interview_Questions_Review._002DFS;

/**
 * @Author: 吕庆龙
 * @Date: 2020/3/7 17:37
 * <p>
 * https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/ju-zhen-zhong-de-zui-chang-di-zeng-lu-jing-by-leet/
 */
public class _0329 {

    public static void main(String[] args) {
        _0329 test = new _0329();

        int[][] nums = {
        {3,4,5},
            {3,2,6},
                {2,2,1}
        };
        test.longestIncreasingPath(nums);

    }


    private int m, n;
    int[][] cache;
    private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

    /**
     * 记忆化dfs,记忆化在代码中提现在cache这个数组
     */
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix.length == 0) return 0;
        m = matrix.length; n = matrix[0].length;
        cache = new int[m][n];
        int ans = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                ans = Math.max(ans, dfs(matrix, i, j));
        return ans;
    }

    private int dfs(int[][] matrix, int i, int j) {
        //下面这个过程也可以称为减枝
        if (cache[i][j] != 0)
            return cache[i][j];
        for (int[] d : dirs) {
            int x = i + d[0], y = j + d[1];
            if (0 <= x && x < m && 0 <= y && y < n && matrix[x][y] > matrix[i][j])
                cache[i][j] = Math.max(cache[i][j], dfs(matrix, x, y));
        }
        return ++cache[i][j];
    }

}
